package Hot_100;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 题目：
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 * intervals 根据 intervals[i][0] 按 升序 排列
 *
 * 解题思路：
 * 法1.可以将newInterval整合到intervals,然后再按第一个元素升序排序，这样就和56题解法一样了
 * 法2.分为三个区域: 1)区间右边界小于新区间的左边界，直接加入res结果数组即可
 *                2)与新区间存在覆盖的这部分区间，需要进行合并
 *                3）区间左边界大于新区间的右边界，直接加入res结果数组即可
 */
public class T57_insert {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][]; //res为结果集，为保证长度足够，故为 intervals.length + 1

        if (intervals.length == 0) {
            res[0] = newInterval;
            return res;
        }

        int i = 0, index = 0;
        while (i<intervals.length&&intervals[i][1]<newInterval[0]) {
            res[index++] = intervals[i++];
        }

        while (i < intervals.length && (intervals[i][1] >= newInterval[0]) && (intervals[i][0] <= newInterval[1])) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);  //第一次循环就可以知道最小值
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);  //最后一次循环才知道最大值
            i++;
        }

        res[index++] = newInterval;

        while (i < intervals.length) {
            res[index++] = intervals[i];
            i++;
        }

        return Arrays.copyOf(res, index); //拷贝结果集的0-index-1即为所求的数组
    }
}
